The invention relates to cryptic devices and more particularly to a cryptic device for encoding and decoding a data signal in accordance with user selected keys.
Remote terminal banking, of the type which utilizes automatic teller machines and credit card automatic currency dispensers, utilizes credit cards which have magnetically encoded stripes of data positioned on a surface of the card. The data is encoded in such a manner as to make alteration of the encoded data difficult. A number of prior art machines utilize a temporary code, that is, each time the card is read by the machine the old code is removed and a new code substituted. Scrambling of the code with a changing key helps to minimize unauthorized access to the currency dispensing machines.
A prior art patent of interest is U.S. Pat. No. 3,662,343 entitled "Credit Card Automatic Currency Dispenser", by K. S. Goldstein et al. In operation, the scrambling device used in the reference patent encodes the clear text data by dividing the complete code phrase into fixed-length words. Empty spaces in a fixed-length word are filled with random letters. The fixed-length words are then transported according to a transposition key. Next a character substitution is performed, for example, by replacing each letter by the next letter in alphabetical order. Finally the letters of each of the word groups are transposed according to a character transposition key. The end result of this scrambling is to provide a system code which has a probability of being broken of 3.times.10.sup.16.
Another prior art technique for cryptically encoding is disclosed in U.S. Pat. No. 3,506,783 entitled "Key Material Generator" by I. Mo et al. and U.S. Pat. No. 3,522,374 entitled "Ciphering Unit" by P. R. Abrahamsen et al. Both of these patents disclose a pseudo-random key generator for generating a long sequence of non-linear pseudo-random bits. Clear text data is modulo-two added to a portion of the pseudo-random key signal to provide the encoded signal. The pseudo-random key generator utilizes a plurality of shift registers with non-linear feedback circuits. The long sequence of random bits is produced by selecting, by means of pins on a pinboard, certain outputs from each of the plurality of shift registers.
Encoding techniques which utilize a long sequence linear pseudo-random key as the sole means of encoding were believed to be reasonably secure from unauthorized decoding, but it has recently been discovered that if a string of encoded data of sufficient length could be obtained then the long sequence, linear pseudo-random key could be determined by a mathematical attack or a cipher text analysis.
To prevent or minimize the possibility of such a determination the present invention utilizes both a bit substitution process and a bit transposition process. In the present invention the bit outputs from a plurality of linear shift registers are combined in a non-linear sequence generator to provide a bit substitution signal which signal is a long, non-linear pseudo-random sequence bit signal. The bit outputs from the plurality of linear shift registers are programmably combined in the non-linear sequence generator according to a first program key. The bit substitution signal is then logically combined with the clear text data signal to provide a partially encoded signal. A bit shuffler then shuffles the position of the bits in the partially encoded signal so as to perform the bit transposition process, and to provide the completely encoded signal. The shuffle position of the bit is programmably controlled in the shuffle register according to a second program key. The "layering" of a bit substitution process with a bit transposition process without making the intermediate results known makes key recovery by mathematical attack or by cipher text analysis so time consuming that the key configuration would probably have been changed in the interim. The intent, of course, is to make the only possible approach to decoding be by trial and error, and then make the number of trials required astronomical.
A target was selected such that if one key configuration were tried every microsecond for 10 years there should be less than one change in a million of having tried the correct configuration. If this goal could be met, it was assumed that the enciphering mechanism would be sufficiently complex for the needs of an automatic teller terminal. There are 3.1536 .times. 10.sup.14 microseconds in 10 years. If the number of possible key configurations were greater than 3.2 .times. 10.sup.20 the goal would be achieved.
In the preferred embodiment of the present invention the encrypter uses a 16 bit linear shift register with a random synchronizing configuration. This provides 6.5535 .times. 10.sup.4 possible starting configurations. The shift register is used in conjunction with one or more non-linear sequence generators whose input connections are (programmed) user selected. There are 16!/(2! .times. 7!) or 2.07 .times. 10.sup.9 possible configurations of the inputs to each non-linear sequence generator. Finally, the message is segmented into 56 bit blocks and these bits are shuffled (programmed) by user selection. This provides 28! .times. 2.sup.28 or 8.18 .times. 10.sup.37 possible shuffle configurations. Multiplying 6.5535 .times. 10.sup.4 .times. 2.07 .times. 10.sup.9 .times. 8.18 .times. 10.sup.37 equals 1.11 .times. 10.sup.52 total possible configurations. This far surpasses the necessary target complexity.